//
// Created by liushuai on 2021/1/17.
//

#include "zigzagLevelOrder.h"
std::vector<std::vector<int> > zigzagLevelOrder(TreeNode* root){
    std::vector<std::vector<int>>result;
    if(!root)
        return result;
    else{
        std::stack<TreeNode*> odd;
        std::stack<TreeNode*> even;
        even.push(root);
        while(!even.empty()||!odd.empty()){
            int queue_size = even.size();
            std::vector<int> layers;
            for(int i=0;i<queue_size;i++){
                TreeNode* current = even.top();
                even.pop();
                layers.push_back(current->val);
                if(current->left)
                    odd.push(current->left);
                if(current->right)
                    odd.push(current->right);
            }
            if(!layers.empty()){
                result.push_back(layers);
                layers.clear();
            }
            int stack_size = odd.size();
            for(int i=0;i<stack_size;i++){
                TreeNode* current = odd.top();
                odd.pop();
                layers.push_back(current->val);
                if(current->right)
                    even.push(current->right);
                if(current->left)
                    even.push(current->left);
            }
            if(!layers.empty()){
                result.push_back(layers);
                layers.clear();
            }

        }
        return result;


    }
}